Communication between distant stations or nodes, for example communication between nodes in a satellite network orbiting the earth, presents many requirements that have not previously been encountered in communication or computer networks. Most such communication networks are expected to be based in space and to consist of thousands of satellites orbiting the earth at various altitudes and inclinations. Such satellites are constantly moving in and out of line of sight of each other and, when engaged in a battle, are subject to all kinds of threats, ranging from link jamming to total destruction. The dynamic and volatile nature of such networks poses a great challenge to network management, requiring techniques that adapt to topological changes and that can survive threats.
In some situations, it may be desired to transmit a packet of data from one node to one specific other node. Such transmissions are referred to as "point-to-point". In other situations, it may be desired to send data from a sensor node in the network to all other nodes in the network, or to all the nodes in a subnetwork of the network. By way of illustration, in a defensive military environment, a subnetwork of sensor nodes may be in high earth orbits, as depicted in FIG. 1, while a subnetwork of weapon nodes may be in low earth orbits, as depicted in FIG. 2. It may be necessary to broadcast a packet of data from a sensor node in the high earth orbit to every weapon node in the low earth orbit. Such a transmission from one node to every node of a subnetwork rather than to a specific one or few of those nodes, is referred to as a "broadcast"; i.e., a transmission from the one node that is "broadcast" to all those other nodes. In the following description, then, "broadcast" refers to such a transmission from one node intended for all of a network or subnetwork of nodes.
In a broadcast mode, packets of data can be guided by a broadcast routing algorithm installed at each node to relay the data packets from node to node over point-to-point links so as to be received by all nodes that are reachable from the source node. This mode of broadcasting has been done before in military or commercial packet switching networks. However, in some defense scenarios, data generated by all the sensor sources can total hundreds of thousands of packets per second. Assured broadcasting of such a quantity of data requires that, in addition to being adaptive and survivable, the broadcast routing algorithm be able to handle a very high traffic load without exacting a heavy toll from the network resources.
There are many existing algorithms for routing broadcast packets in a packet switching network; however, none has been found which offers a satisfactory combination of good performance and low cost. Some algorithms excel in the selection of least delay routes at the expense of bandwidth memory, or computing power. Others sacrifice routing optimality for low overhead cost. Previous work on broadcast routing algorithms is described, for example, in Computer Networks, by A. S. Tanenbaum, Prentice Hall, Englewood Cliffs, N.J., 1981, and in "Reverse Path Forwarding of Broadcast Packets," by Y. K. Dalal and R. M. Metcalfe, Communications of the ACM, Vol. 21, pp. 1040-1048, December 1978.
One such existing algorithm is known as separate destination addressing. If the network is already equipped with a point-to-point routing algorithm, the obvious approach to broadcast routing is to have the source generate a copy of the broadcast packet for each destination and then to use point-to-point routing to deliver each copy. This approach makes good use of existing hardware; however, since routes to different destinations often overlap, most relaying nodes will receive, process and transmit the same packet over and over again. The abundance of duplicates represents a waste of bandwidth and is likely to create a high level of congestion, especially in areas close to the source.
Another approach to broadcast routing is to carry multiple destination addresses with each packet. When a broadcast packet is generated or received at a node, it partitions the remaining list of destinations, grouping together destinations that map to the same outgoing link in its point-to-point routing table. For each such group the node generates a copy of the broadcast packet, attaches the group's destination list, and forwards the packet on the selected outgoing link. As the broadcast propagates farther away from the source, the destination list gets smaller until there is no destination remaining. The packets follow the branches of a spanning tree rooted at the source, although information on the spanning tree is not explicitly stored at each node.
Forwarding broadcast packets along branches of a spanning tree has the advantage of generating an optimal number of packet copies; this number is exactly equal to the number of reachable destinations. However, the disadvantage of multidestination addressing lies in the long destination field. A bit map implementation requires as many bits as there are nodes. For networks with thousands of nodes, the high ratio of overhead bits to data bits is a drawback that is not easy to overcome. Furthermore, the performance of this algorithm is tied to that of the underlying point-to-point routing algorithm. If the point-to-point routes are inconsistent, unstable or slow to adapt, the same effects will be exhibited in the broadcast routes.
Constrained flooding is a technique in which an arriving packet that has not been seen before is copied and forwarded on all outgoing links except the link on which it arrived. Packets that have been seen are simply discarded. To keep track of already seen packets, a sequence number is assigned to each packet by the source node, and a constraint table or bit map is maintained at each node to log received packets. The log for a particular packet has to remain in the constraint table for some time, at least for the duration of the broadcast, before the log can be cleared and reused. The size of the constraint table is thus proportional to this predefined time for packets to live, the maximum traffic generation rate by all sources, and the total number of sources. For the architecture of a large network, the constraint table can take up a large chunk of memory. Estimates of millions of bits are not too exaggerated. On top of this hefty memory requirement, constrained flooding also generates a large number of packet copies--(N)(L-1)+1 copies, where N is the number of nodes in the network and L is the number of links per node.
As for advantages, constrained flooding is most noted for its robustness. Packet copies that seem to be such a waste at first glance are much needed to replace lost copies. In a simulation of a 300-node network, the algorithm delivered packets to 99.83% of the destination nodes in spite of a 10% packet error rate. Constrained flooding is also known for its selection of best routes. The algorithm always finds the shortest routes possible, and its routes adapt instantaneously to changes in the network.
The least consumption of bandwidth in broadcasting is achieved with minimum spanning tree forwarding, in which packets are forwarded along branches of a spanning tree stored explicitly at each node. If the spinning tree has shortest paths from the source of the broadcast to all destinations, delay is also minimized. The biggest problem in minimum spanning tree forwarding is in determining how the nodes in the network are to generate and maintain such a tree for each source.
One accepted solution is to allow each node access to a global topology database. Every node generates and receives frequent topology updates which include not only changes in the topology but also changes in the link metric. From the information contained in its local copy of the database, each node uses the Dijkstra's shortest path first algorithm to independently compute minimum spanning trees, each one rooted at a different source. This algorithm is discussed in the above-cited article by Dalal and Metcalfe. This computation has a complexity in the order of (SN.sup.2) operations, where S is the number of sources, and N the number of nodes in the network. For thousands of nodes and hundreds of sources, the amount of computation required in this approach is quite demanding. Moreover, keeping the distributed database consistent and up to date is not an easy task in a hostile environment. The success or failure of this task has a tremendous effect on the quality of the routes computed.
If outgoing links for any destination are taken from every point-to-point routing table in the network and joined together, they form a spanning tree from all nodes to the chosen destination. This fact is cleverly exploited in reverse path forwarding. A node forwards a received broadcast packet on all links except the incoming link if and only if the incoming link is the same link the node would use to send an addressed packet back to the source of the broadcast. Thus, this broadcast routing algorithm also makes use of a spanning tree, but this time the tree has shortest reverse paths; i.e., paths from the destinations to the source.
This approach has both advantages and disadvantages. The principal advantage is that there is no need to compute trees since tree branches are readily available in point-to-point routing tables. The major disadvantage is that the trees are inverted, implying that they may not yield shortest paths from the source to the destinations. Also, links must be flooded with packet copies in the hope that neighbors that are not part of the tree will stop the flood, although this undesirable situation can be corrected by having neighbors exchange their routing tables.